package _11_整理题目._0_工具集;

import org.junit.Test;

import java.security.PublicKey;
import java.util.*;

/**
 * https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/
 * https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix/
 *
 * 排序，写比较器：Comparator  compare( , )
 *      一维数组排序 int[]
 *      二维多行数组排序 int[][]
 *      最大堆，最小堆的初始化
 *      List<int[]> 排序
 *      List<Integer> 排序
 *      List<String> 排序
 *
 *      最大堆，最小堆，自然排序：Comparable  compareTo( )，见合并多个链表
 *
 * 思路：
 *      使用匿名类 Comparator，
 *      使用 lambda 表达式
 *
 *
 * 集合转数组：int[]   String[]
 *      将 Integer[] 转 int[]
 *      将各种集合 List<Integer>, Set<Integer>, Stack<Integer> 等 转为 int[]
 *      将各种集合 List<String>, Set<String>, Stack<String> 等 转为 String[]
 * 思路：
 *      暴力新建对应数组，再逐个复制转换，对 int[] String[] 都适用，但是费时
 *      对 int[] 先将集合转为 stream 再转为 int 最后调用 toArray()，按流程处理
 *      对于 String[] 直接调用 Xxx.toArray(new String[Xxx.size()])
 *
 * steam() 流
 *      数组，集合 转为流：Xxx.stream()  Arrays.stream(arr)
 *      常用的流处理方法：sort() mapToInt() distinct()
 *      收集成 数组 list：.toArray()  .collect(Collectors.toList())
 *
 * 打印一维数组：
 *      System.out.println(Arrays.toString(array));
 * 打印 list :
 *      System.out.println(list);
 */
public class _05_排序_比较器_stream_转数组 {

    @Test // int[][3] 二维 3 列排序，先按第三列增序，再按第二列降序
    public void two() {
        int[][] array = {
                {3,6,9},
                {1,5,8},
                {2,5,9},
                {3,5,2},
        };
        // o1 = [ a, b, c ]   !!! 写出数组内容，不要写错
        Arrays.sort(array, (o1, o2) -> {
            if (o1[2] != o2[2]) {
                return o1[2] - o2[2];
            } else {
                return o2[1] - o1[1];
            }
        });
    }

    @Test   // 二维数组，[下标，内容]，按字符串字典序排序，compareTo
    public void testString() {
        String[] strings = {"3304661051423","2018238485950","1935621349877",
                "2984690475337","7947119117460","3304661051423","6225638668551",
                "3316097971691","2718204690699","3117171030477","0603601443179"};
        String[][] array = new String[strings.length][2];
        for (int j = 0; j < strings.length; j++) {
            array[j][0] = String.valueOf(j);
            array[j][1] = strings[j];
        }

        // o1 = [ i, strings[i] ]   !!! 写出数组内容，不要写错
        Arrays.sort(array, (o1, o2) -> {
            if (!(o1[1].equals(o2[1]))) {
                return o1[1].compareTo(o2[1]); // 字典升序
            } else {
                return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]);
            }
        });
    }

    @Test   // 类的方式比较，[下标，内容]，使用 treeSet
    public void tesThree() {
        String[] strings = {"3304661051423","2018238485950","1935621349877",
                "2984690475337","7947119117460","3304661051423","6225638668551",
                "3316097971691","2718204690699","3117171030477","0603601443179"};

    }


    @Test // 一维排序
    public void oneTest() {
        int[] ints = {2, 5, 1, 8, 4};
        Integer[] integers = {2, 5, 1, 8, 4};
        // 增序
        Arrays.sort(ints);
        int n = ints.length;
        for (int i=0, j=n-1; i<j; i++,j--) {
            int tmp = ints[i];
            ints[i] = ints[j];
            ints[j] = tmp;
        }
        Arrays.sort(integers);

        // 逆序，使用比较器，不能是基本类型
        // Arrays.sort(ints, Collections.reverseOrder());// 编译不通过
        Arrays.sort(integers, Collections.reverseOrder()); // 使用集合的逆序比较器
        Arrays.sort(integers, new Comparator<Integer>() {  // 自己写一个匿名实现类比较器
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        Arrays.sort(integers, ((o1, o2) -> o2-o1)); // 自己写一个匿名实现类比较器 lambda 表达式

        // 转数组
        int[] result = Arrays.stream(integers)
                .mapToInt(Integer::valueOf)
                .toArray();
        System.out.println(Arrays.toString(result));
    }

    @Test // int[][3] 二维 3 列排序，先按第三列增序，再按第二列降序，然后再翻过
    public void twoTest() {
        int[][] array = {
                {3,6,9},
                {1,5,8},
                {2,5,9},
                {3,5,2},
        };
        // 自己写一个匿名实现类比较器
        Arrays.sort(array, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[2] != o2[2]) {
                    return o1[2] - o2[2];
                } else {
                    return o2[1] - o1[1];
                }
            }
        });
        for (int[] arr : array) {
            System.out.println(Arrays.toString(arr));
        }
        System.out.println();

        // 翻转 自己写一个匿名实现类比较器 lambda 表达式
        Arrays.sort(array, (o1, o2) -> {
            if (o1[2] != o2[2]) {
                return o2[2] - o1[2];
            } else {
                return o1[1] - o2[1];
            }
        });
        for (int[] ints : array) {
            System.out.println(Arrays.toString(ints));
        }
    }
    
    @Test
    public void PriorityQueueTest() {
        // 初始化一个 增序的 小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        // 初始化一个 降序的 大根堆
        PriorityQueue<Integer> queue1 = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        PriorityQueue<Integer> queue2 = new PriorityQueue<>((o1, o2) -> o2 - o1);

        queue.add(1);
        queue.add(2);
        queue.add(3);
        System.out.println(queue.peek());

        queue1.add(1);
        queue1.add(2);
        queue1.add(3);
        System.out.println(queue1.peek());

        queue2.add(1);
        queue2.add(2);
        queue2.add(3);
        System.out.println(queue2.peek());
    }

    @Test
    public void ComparatorTest() {
        // 自然比较器 Comparable，一个类实现这个接口，并重写 compareTo 方法
        // 当把这个类放到 优先队列 等有比较的数据结构中，会自动调用 compareTo 对所有对象自然排序

        class Node implements Comparable<Node> {
            int val;

            public Node(int val) {
                this.val = val;
            }

            @Override
            public int compareTo(Node node) {
                return this.val - node.val;
            }
        }

        PriorityQueue<Node> queue = new PriorityQueue<>((n1,n2)->n2.val-n1.val);
        queue.offer(new Node(3));
        queue.offer(new Node(1));
        queue.offer(new Node(5));
        queue.offer(new Node(8));
        queue.offer(new Node(2));
        while (!queue.isEmpty()) {
            System.out.println(queue.poll().val);
        }
    }

    @Test
    public void ListToArray() {
        List<int[]> list = new ArrayList<>();
        list.add(new int[]{1,5});
        list.add(new int[]{6,8});
        list.add(new int[]{3,4});
        int[][] res = list.toArray(new int[list.size()][]);

        for (int[] re : res) {
            System.out.println(Arrays.toString(re));
        }
    }
}
